43. 字符串相乘

Similar Question

leading to the advanced question

Solution Tips

方案一: 模拟, 先相乘后相加

/**
 * @param {string} num1
 * @param {string} num2
 * @return {string}
 */
var multiply = function(num1, num2) {
    if (num1 === '0' || num2 === '0') {
        return '0';
    };

    const addend = [];
    for (let i = num2.length - 1; i >= 0; i--) {
        const result = singleFactor(num1, num2[i], '0'.repeat(num2.length - 1 - i));
        addend.push(result);
    }

    // addend 循环相加? 也可以一次性加完, 但是时间复杂度不会差太多, 先简单的来吧
    return addend.reduce((acc, val) => addition(acc, val))
};

function singleFactor(num1, factor, padding) {
    // 参考之前的逻辑, 不用预填充, 用 rest 模拟
    let i = num1.length - 1;
    let rest = 0;

    const res = [padding];

    while (i >= 0 || rest !== 0) {
        const x = i >= 0 ? +num1[i] : 0;

        const result = x * factor + rest;
        res.push(result % 10);
        rest = Math.floor(result / 10);
        i--;
    }

    return res.reverse().join('');
}

function addition(num1, num2) {
    let i = num1.length - 1;
    let j = num2.length - 1;
    let rest = 0;
    let ans = [];

    while (i >= 0 || j >= 0 || rest !== 0) {
        const x = i >= 0 ? +num1[i] : 0;
        const y = (j >= 0) ? +num2[j] : 0;

        const result = x + y + rest;
        ans.push(result % 10);
        rest = Math.floor(result / 10);
        i--;
        j--;
    }

    return ans.reverse().join('')
}

console.log(multiply("999", "0"))
console.log(multiply("456", "77"))

方案二: 模拟竖式乘法

  var multiply = function(num1, num2) {
    let result = []
    // m 长度 * n 长度，总长度不会超过 m + n + 1;
    for (let i = num1.length-1; i >= 0; i--) {
      for (let j = num2.length-1; j >= 0; j--) {
        let s = num1[i]*1 * num2[j]*1 + (result[i + j + 1] || 0)
        result[i + j + 1] = s % 10
        // 位操作取整，进位
        result[i + j] = (s / 10 | 0) + (result[i + j] || 0)
      }
    }
  
    while(result[0] === 0) result.shift()
    return result.join("") || "0";
  }